Search for: All records

Efficient multi-robot task allocation (MRTA) is fundamental to various time-sensitive applications such as disaster response, warehouse operations, and construction. This paper tackles a particular class of these problems that we call MRTA-collective transport or MRTA-CT – here tasks present varying workloads and deadlines, and robots are subject to flight range, communication range, and payload constraints. For large instances of these problems involving 100s-1000’s of tasks and 10s-100s of robots, traditional non-learning solvers are often time-inefficient, and emerging learning-based policies do not scale well to larger-sized problems without costly retraining. To address this gap, we use a recently proposed encoder-decoder graph neural network involving Capsule networks and multi-head attention mechanism, and innovatively add topological descriptors (TD) as new features to improve transferability to unseen problems of similar and larger size. Persistent homology is used to derive the TD, and proximal policy optimization is used to train our TD-augmented graph neural network. The resulting policy model compares favorably to state-of-the-art non-learning baselines while being much faster. The benefit of using TD is readily evident when scaling to test problems of size larger than those used in training. 

As city populations continue to rise, urban air mobility (UAM) seeks to provide much needed relief from traffic congestion. UAM is enforced by electrical vertical takeoff and landing (eVTOL) vehicles, which operate out of a vertiport, akin to the relationship between planes and airports. The vertiport has an air traffic controller (ATC) tasked with managing each eVTOL, ensuring they reach their destinations on time and safely. This task allocation problem can be difficult due to inadvertent issues such as mechanical failure, inclement weather, collisions, among other uncertainties that may arise. This paper provides a novel solution to this Urban Air Mobility - Vertiport Schedule Management (UAM-VSM) problem through the utilization of graph convolutional networks (GCNs). GCNs allow us to add abstractions of the vertiport space and eVTOL space as graphs, and aggregate information for a centralized ATC agent to help generalize the environment. We use Unreal Engine combined with Airsim for high fidelity simulation. The proposed GRL agent will be trained in an environment without extra uncertainties and then tested with and without those uncertainties. The performance will be examined side by side with a random and first come first serve (FCFS) baseline. 

This paper introduces a new graph neural network architecture for learning solutions of Capacitated Vehicle Routing Problems (CVRP) as policies over graphs. CVRP serves as an important benchmark for a wide range of combinatorial planning problems, which can be adapted to manufacturing, robotics and fleet planning applications. Here, the specific aim is to demonstrate the significant real-time executability and (beyond training) scalability advantages of the new graph learning approach over existing solution methods. While partly drawing motivation from recent graph learning methods that learn to solve CO problems such as multi-Traveling Salesman Problem (mTSP) and VRP, the proposed neural architecture presents a novel encoder-decoder architecture. Here the encoder is based on Capsule networks, which enables better representation of local and global information with permutation invariant node embeddings; and the decoder is based on the Multi-head attention (MHA) mechanism allowing sequential decisions. This architecture is trained using a policy gradient Reinforcement Learning process. The performance of our approach is favorably compared with state-of-the-art learning and non-learning methods for a benchmark suite of Capacitated-VRP (CVRP) problems. A further study on the CVRP with demand uncertainties is conducted to explore how this Capsule-Attention Mechanism architecture can be extended to handle real-world uncertainties by embedding them through the encoder.